<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222" media="(prefers-color-scheme: light)">
<meta name="theme-color" content="#222" media="(prefers-color-scheme: dark)"><meta name="generator" content="Hexo 5.4.2">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.1.1/css/all.min.css" integrity="sha256-DfWjNxDkM94fVBWx1H5BMMp0Zq7luBlV8QRcSES7s+0=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"mathieulin.gitee.io","root":"/","images":"/images","scheme":"Gemini","darkmode":true,"version":"8.12.1","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":false,"style":null},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"manual","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="[TOC] C1A 主定理 12345678910111213141516171819#include &lt;bits&#x2F;stdc++.h&gt;using namespace std;int t, a, b, k;int main()&amp;#123;	scanf(&quot;%d&quot;, &amp;t);	while(t--)&amp;#123;		scanf(&quot;%d%d%d&quot;,">
<meta property="og:type" content="article">
<meta property="og:title" content="Mathieu&#39;s blog">
<meta property="og:url" content="https://mathieulin.gitee.io/2023/09/22/super2121/index.html">
<meta property="og:site_name" content="Mathieu&#39;s blog">
<meta property="og:description" content="[TOC] C1A 主定理 12345678910111213141516171819#include &lt;bits&#x2F;stdc++.h&gt;using namespace std;int t, a, b, k;int main()&amp;#123;	scanf(&quot;%d&quot;, &amp;t);	while(t--)&amp;#123;		scanf(&quot;%d%d%d&quot;,">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//Users/15128/AppData/Roaming/Typora/typora-user-images/image-20230922095545132.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//Users/15128/AppData/Roaming/Typora/typora-user-images/image-20230922100302735.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922100525536.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922100849235.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922101517436.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922102005428.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922103338426.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922104158887.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922104257685.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922104542514.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922105924398.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922110108059.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922111251560.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922112139921.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922142257679.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922142531892.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922144420311.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922145722701.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922151222239.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922151900640.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922141545470.png">
<meta property="og:image" content="https://mathieulin.gitee.io/.io//image-20230922135427281.png">
<meta property="article:published_time" content="2023-09-22T07:25:29.984Z">
<meta property="article:modified_time" content="2023-09-22T07:49:50.974Z">
<meta property="article:author" content="Mathieu Lin">
<meta property="article:tag" content="lzh">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://mathieulin.gitee.io/.io//Users/15128/AppData/Roaming/Typora/typora-user-images/image-20230922095545132.png">


<link rel="canonical" href="https://mathieulin.gitee.io/2023/09/22/super2121/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"https://mathieulin.gitee.io/2023/09/22/super2121/","path":"2023/09/22/super2121/","title":""}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title> | Mathieu's blog</title>
  




<link rel="dns-prefetch" href="https://blog-commeny-mh5e4d5jo-mathieulin.vercel.app">
  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
<link rel="alternate" href="/atom.xml" title="Mathieu's blog" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">Mathieu's blog</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">lzhow的debug路程</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li><li class="menu-item menu-item-schedule"><a href="/schedule/" rel="section"><i class="fa fa-calendar fa-fw"></i>日程表</a></li><li class="menu-item menu-item-sitemap"><a href="/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a></li><li class="menu-item menu-item-commonweal"><a href="/404/" rel="section"><i class="fa fa-heartbeat fa-fw"></i>公益 404</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#C1"><span class="nav-number">1.</span> <span class="nav-text">C1</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#A-%E4%B8%BB%E5%AE%9A%E7%90%86"><span class="nav-number">1.1.</span> <span class="nav-text">A 主定理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#B-%E4%B8%80%E5%85%83%E5%A4%9A%E9%A1%B9%E5%BC%8F"><span class="nav-number">1.2.</span> <span class="nav-text">B 一元多项式</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A8%A1%E8%BF%90%E7%AE%97"><span class="nav-number">1.3.</span> <span class="nav-text">模运算</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#D-%E6%97%A5%E6%9C%9F%E7%BB%9F%E8%AE%A1"><span class="nav-number">1.4.</span> <span class="nav-text">D 日期统计</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#E-%E5%8D%95%E8%AF%8D%E6%B8%B8%E6%88%8F"><span class="nav-number">1.5.</span> <span class="nav-text">E 单词游戏</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%80%86%E5%BA%8Fk%E5%80%8D%E5%AF%B9"><span class="nav-number">1.6.</span> <span class="nav-text">逆序k倍对</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#E1"><span class="nav-number">2.</span> <span class="nav-text">E1</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#A-%E4%BD%A0%E8%BF%98%E8%AE%B0%E5%BE%97%E6%88%91%E5%98%9B-%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%8A%A0%E6%B3%95"><span class="nav-number">2.1.</span> <span class="nav-text">A 你还记得我嘛~(多项式加法)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#B-n%E6%AC%A1%E6%96%B9%E7%9A%84%E5%92%8C"><span class="nav-number">2.2.</span> <span class="nav-text">B n次方的和</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A4%9A%E8%B7%AF%E5%BD%92%E5%B9%B6"><span class="nav-number">2.3.</span> <span class="nav-text">多路归并</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#D-%E9%9A%8F%E6%9C%BA%E6%95%B0"><span class="nav-number">2.4.</span> <span class="nav-text">D 随机数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BB%84%E5%90%88%E6%95%B0"><span class="nav-number">2.5.</span> <span class="nav-text">组合数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#F-%E8%8E%AB%E5%8D%A1%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91%E9%AD%94%E6%B3%95"><span class="nav-number">2.6.</span> <span class="nav-text">F 莫卡的二叉树魔法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2%E7%9A%84%E5%B9%82"><span class="nav-number">2.7.</span> <span class="nav-text">2的幂</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#I-XIAO7-%E7%9A%84%E5%9C%B0%E5%9B%BE"><span class="nav-number">2.8.</span> <span class="nav-text">I XIAO7 的地图</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#C2"><span class="nav-number">3.</span> <span class="nav-text">C2</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B9%B3%E9%9D%A2%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9"><span class="nav-number">3.1.</span> <span class="nav-text">平面最近点对</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#B-%E6%9C%80%E5%A4%A7%E5%A0%86%E7%9A%84%E5%AE%9E%E7%8E%B0"><span class="nav-number">3.2.</span> <span class="nav-text">B 最大堆的实现</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#E2"><span class="nav-number">4.</span> <span class="nav-text">E2</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#A-%E7%AE%80%E5%8D%95%E7%9A%84%E5%8F%AF%E5%88%A0%E5%A0%86"><span class="nav-number">4.1.</span> <span class="nav-text">A 简单的可删堆</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#B-%E9%80%92%E5%BD%92%E9%93%BA%E7%93%B7%E7%A0%96"><span class="nav-number">4.2.</span> <span class="nav-text">B 递归铺瓷砖</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#C-%E5%AD%90%E9%9B%86"><span class="nav-number">4.3.</span> <span class="nav-text">C 子集</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%B1%89%E8%AF%BA%E5%A1%94"><span class="nav-number">4.4.</span> <span class="nav-text">汉诺塔</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#C7"><span class="nav-number">5.</span> <span class="nav-text">C7</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#B-%E6%90%AC%E7%A0%96%E9%97%AE%E9%A2%98"><span class="nav-number">5.1.</span> <span class="nav-text">B 搬砖问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#C-Bellalabella-%E4%B8%8E%E4%B8%AD%E4%BD%8D%E6%95%B0"><span class="nav-number">5.2.</span> <span class="nav-text">C Bellalabella 与中位数</span></a></li></ol></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">Mathieu Lin</p>
  <div class="site-description" itemprop="description">这是一个记载了lzhow传奇的一生的博客</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">14</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">8</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
        <span class="site-state-item-count">9</span>
        <span class="site-state-item-name">标签</span>
      </div>
  </nav>
</div>
  <div class="links-of-author site-overview-item animated">
      <span class="links-of-author-item">
        <a href="https://github.com/mathieulin" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;mathieulin" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:19241032@buaa.edu.cn" title="E-Mail → mailto:19241032@buaa.edu.cn" rel="noopener" target="_blank"><i class="fab fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://121.199.35.110/" title="Todo → http:&#x2F;&#x2F;121.199.35.110&#x2F;" rel="noopener" target="_blank">Todo</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://noietch.cn:88/" title="House → http:&#x2F;&#x2F;noietch.cn:88&#x2F;" rel="noopener" target="_blank">House</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://vkceyugu.cdn.bspapp.com/VKCEYUGU-05d97c93-6101-4c53-8659-f5cf79396b93/0cdfad7c-f758-49ca-becf-6483b8fe95d5.apk" title="Douzero → https:&#x2F;&#x2F;vkceyugu.cdn.bspapp.com&#x2F;VKCEYUGU-05d97c93-6101-4c53-8659-f5cf79396b93&#x2F;0cdfad7c-f758-49ca-becf-6483b8fe95d5.apk" rel="noopener" target="_blank">Douzero</a>
      </span>
      <span class="links-of-author-item">
        <a href="/atom.xml" title="rss → &#x2F;atom.xml"><i class="fa fa-rss fa-fw"></i>rss</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://mathieulin.github.io/myblog" title="Another-blog → https:&#x2F;&#x2F;mathieulin.github.io&#x2F;myblog" rel="noopener" target="_blank">Another-blog</a>
      </span>
  </div>



        </div>
      </div>
    </div>
    <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=330 height=86 src="//music.163.com/outchain/player?type=2&id=1951671851&auto=1&height=66"></iframe>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2023/09/22/super2121/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content=" | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>
      

      <time title="创建时间：2023-09-22 15:25:29 / 修改时间：15:49:50" itemprop="dateCreated datePublished" datetime="2023-09-22T15:25:29+08:00">2023-09-22</time>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2023/09/22/super2121/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2023/09/22/super2121/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <p>[TOC]</p>
<h1 id="C1"><a href="#C1" class="headerlink" title="C1"></a>C1</h1><h2 id="A-主定理"><a href="#A-主定理" class="headerlink" title="A 主定理"></a>A 主定理</h2><p><img src="/.io//Users\15128\AppData\Roaming\Typora\typora-user-images\image-20230922095545132.png" alt="image-20230922095545132"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, a, b, k;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--)&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>, &amp;a, &amp;b, &amp;k);</span><br><span class="line">		<span class="type">long</span> <span class="type">long</span> x = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">if</span>(b &gt; <span class="number">1</span>)&#123;</span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= k &amp;&amp; x &lt;= a;i++) x *= b;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(a == x) <span class="built_in">puts</span>(<span class="string">&quot;n^k\\log n&quot;</span>);</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(a &gt; x) <span class="built_in">puts</span>(<span class="string">&quot;n^&#123;\\log_ba&#125;&quot;</span>);</span><br><span class="line">		<span class="keyword">else</span> <span class="built_in">puts</span>(<span class="string">&quot;n^k&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="B-一元多项式"><a href="#B-一元多项式" class="headerlink" title="B 一元多项式"></a>B 一元多项式</h2><p><img src="/.io//Users\15128\AppData\Roaming\Typora\typora-user-images\image-20230922100302735.png" alt="image-20230922100302735"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> M 10007</span></span><br><span class="line"><span class="type">long</span> <span class="type">long</span> a[<span class="number">1000001</span>],b[<span class="number">1000001</span>];</span><br><span class="line"><span class="type">long</span> <span class="type">long</span> n,m,x,y,i,t,c;</span><br><span class="line"><span class="function"><span class="type">long</span> <span class="type">long</span> <span class="title">Horner</span><span class="params">(<span class="type">long</span> <span class="type">long</span> *a,<span class="type">long</span> <span class="type">long</span> n,<span class="type">long</span> <span class="type">long</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(n&lt;<span class="number">1</span>)</span><br><span class="line">		<span class="keyword">return</span> a[<span class="number">0</span>] % M;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">		<span class="built_in">return</span> (a[<span class="number">0</span>] % M + (<span class="built_in">Horner</span>(a+<span class="number">1</span>,n<span class="number">-1</span>,x) * x) % M) % M;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;n);</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;=n; i++) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;a[i]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;m);</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;=m; i++) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;b[i]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;c);</span><br><span class="line">	<span class="keyword">while</span>(c--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%lld %lld&quot;</span>,&amp;x,&amp;y);</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%lld\n&quot;</span>,( (<span class="built_in">Horner</span>(a,n,x) % M) * (<span class="built_in">Horner</span>(b,m,y) % M) ) % M );</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="模运算"><a href="#模运算" class="headerlink" title="模运算"></a>模运算</h2><p><img src="/.io//image-20230922100525536.png" alt="image-20230922100525536"></p>
 <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 100086</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> p = <span class="number">1e9</span> + <span class="number">6</span>;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n;</span><br><span class="line"><span class="type">int</span> a[maxn], f[maxn], g[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--)&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;a[i]);</span><br><span class="line">		f[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) </span><br><span class="line">            f[i] = <span class="number">1ll</span> * f[i - <span class="number">1</span>] * a[i] % p;</span><br><span class="line">		g[n + <span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = n;i;i--) </span><br><span class="line">            g[i] = <span class="number">1ll</span> * g[i + <span class="number">1</span>] * a[i] % p;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) </span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, <span class="number">1ll</span> * f[i - <span class="number">1</span>] * g[i + <span class="number">1</span>] % p);</span><br><span class="line">        <span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="D-日期统计"><a href="#D-日期统计" class="headerlink" title="D 日期统计"></a>D 日期统计</h2><p><img src="/.io//image-20230922100849235.png" alt="image-20230922100849235"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> eps 1e-14</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 300005</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">double</span> ld;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">unsigned</span> <span class="type">long</span> <span class="type">long</span> ull;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="type">int</span> <span class="title">read</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> x = <span class="number">0</span>, f = <span class="number">1</span>;</span><br><span class="line">	<span class="type">char</span> ch = <span class="built_in">getchar</span>();</span><br><span class="line">	<span class="keyword">while</span> (ch &gt; <span class="string">&#x27;9&#x27;</span> || ch &lt; <span class="string">&#x27;0&#x27;</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span> (ch == <span class="string">&#x27;-&#x27;</span>)</span><br><span class="line">			f = <span class="number">-1</span>;</span><br><span class="line">		ch = <span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span> (ch &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; ch &lt;= <span class="string">&#x27;9&#x27;</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		x = x * <span class="number">10</span> + ch - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">		ch = <span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> x * f;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">char</span> s[<span class="number">10</span>], t[<span class="number">10</span>];</span><br><span class="line"><span class="type">int</span> y[<span class="number">2</span>], m[<span class="number">2</span>], d[<span class="number">2</span>];</span><br><span class="line"><span class="type">int</span> mx[<span class="number">13</span>] = &#123;<span class="number">0</span>, <span class="number">31</span>, <span class="number">28</span>, <span class="number">31</span>, <span class="number">30</span>, <span class="number">31</span>, <span class="number">30</span>, <span class="number">31</span>, <span class="number">31</span>, <span class="number">30</span>, <span class="number">31</span>, <span class="number">30</span>, <span class="number">31</span>&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">check</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b, <span class="type">int</span> c)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> s[<span class="number">10</span>], t = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">2</span>; i++)</span><br><span class="line">		s[++t] = c % <span class="number">10</span>, c /= <span class="number">10</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">2</span>; i++)</span><br><span class="line">		s[++t] = b % <span class="number">10</span>, b /= <span class="number">10</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">4</span>; i++)</span><br><span class="line">		s[++t] = a % <span class="number">10</span>, a /= <span class="number">10</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">8</span>; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="type">bool</span> f = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = i + <span class="number">1</span>; j &lt;= <span class="number">8</span>; j++)</span><br><span class="line">			<span class="keyword">if</span> (s[j] &lt; s[j - <span class="number">1</span>])</span><br><span class="line">				f = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = i - <span class="number">1</span>; j &gt;= <span class="number">1</span>; j--)</span><br><span class="line">			<span class="keyword">if</span> (s[j] &lt; s[j + <span class="number">1</span>])</span><br><span class="line">				f = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">if</span> (f)</span><br><span class="line">			<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">		f = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = i + <span class="number">1</span>; j &lt;= <span class="number">8</span>; j++)</span><br><span class="line">			<span class="keyword">if</span> (s[j] &gt; s[j - <span class="number">1</span>])</span><br><span class="line">				f = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = i - <span class="number">1</span>; j &gt;= <span class="number">1</span>; j--)</span><br><span class="line">			<span class="keyword">if</span> (s[j] &gt; s[j + <span class="number">1</span>])</span><br><span class="line">				f = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">if</span> (f)</span><br><span class="line">			<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">isleap</span><span class="params">(<span class="type">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> (x % <span class="number">4</span> == <span class="number">0</span> &amp;&amp; x % <span class="number">100</span> != <span class="number">0</span>) || (x % <span class="number">400</span> == <span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">solve</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, s + <span class="number">1</span>), <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, t + <span class="number">1</span>);</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">4</span>; i++)</span><br><span class="line">		y[<span class="number">0</span>] = y[<span class="number">0</span>] * <span class="number">10</span> + s[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">5</span>; i &lt;= <span class="number">6</span>; i++)</span><br><span class="line">		m[<span class="number">0</span>] = m[<span class="number">0</span>] * <span class="number">10</span> + s[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">7</span>; i &lt;= <span class="number">8</span>; i++)</span><br><span class="line">		d[<span class="number">0</span>] = d[<span class="number">0</span>] * <span class="number">10</span> + s[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">4</span>; i++)</span><br><span class="line">		y[<span class="number">1</span>] = y[<span class="number">1</span>] * <span class="number">10</span> + t[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">5</span>; i &lt;= <span class="number">6</span>; i++)</span><br><span class="line">		m[<span class="number">1</span>] = m[<span class="number">1</span>] * <span class="number">10</span> + t[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">7</span>; i &lt;= <span class="number">8</span>; i++)</span><br><span class="line">		d[<span class="number">1</span>] = d[<span class="number">1</span>] * <span class="number">10</span> + t[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span> (y[<span class="number">0</span>] != y[<span class="number">1</span>] || m[<span class="number">0</span>] != m[<span class="number">1</span>] || d[<span class="number">0</span>] != d[<span class="number">1</span>])</span><br><span class="line">	&#123;</span><br><span class="line">		ans += <span class="built_in">check</span>(y[<span class="number">0</span>], m[<span class="number">0</span>], d[<span class="number">0</span>]);</span><br><span class="line">		d[<span class="number">0</span>]++;</span><br><span class="line">		<span class="keyword">if</span> (d[<span class="number">0</span>] &gt; mx[m[<span class="number">0</span>]] + (m[<span class="number">0</span>] == <span class="number">2</span> &amp;&amp; <span class="built_in">isleap</span>(y[<span class="number">0</span>])))</span><br><span class="line">			m[<span class="number">0</span>]++, d[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">if</span> (m[<span class="number">0</span>] &gt; <span class="number">12</span>)</span><br><span class="line">			m[<span class="number">0</span>] = <span class="number">1</span>, y[<span class="number">0</span>]++;</span><br><span class="line">	&#125;</span><br><span class="line">	ans += <span class="built_in">check</span>(y[<span class="number">1</span>], m[<span class="number">1</span>], d[<span class="number">1</span>]);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> t = <span class="number">1</span>, cnt = <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">while</span> (t--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">solve</span>();</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="E-单词游戏"><a href="#E-单词游戏" class="headerlink" title="E 单词游戏"></a>E 单词游戏</h2><p><img src="/.io//image-20230922101517436.png" alt="image-20230922101517436"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">int</span> a[<span class="number">600000</span>][<span class="number">3</span>];</span><br><span class="line"><span class="type">char</span> s[<span class="number">10</span>];</span><br><span class="line"><span class="type">int</span> ans[<span class="number">3</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">tr</span><span class="params">(<span class="type">char</span> s[])</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> res=<span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> len=<span class="built_in">strlen</span>(s);</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;len;i++)</span><br><span class="line">	&#123;</span><br><span class="line">		res=res*<span class="number">27</span>+s[i]-<span class="string">&#x27;a&#x27;</span>+<span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> t,n;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">memset</span>(a,<span class="number">0</span>,<span class="built_in">sizeof</span>(a));</span><br><span class="line">		<span class="built_in">memset</span>(ans,<span class="number">0</span>,<span class="built_in">sizeof</span>(ans));</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;<span class="number">3</span>;j++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">			&#123;</span><br><span class="line">				<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,s);</span><br><span class="line">				a[<span class="built_in">tr</span>(s)][j]++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;<span class="number">27</span>*<span class="number">27</span>*<span class="number">27</span>*<span class="number">27</span>;i++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">if</span>(a[i][<span class="number">0</span>]&amp;&amp;a[i][<span class="number">1</span>]&amp;&amp;a[i][<span class="number">2</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				<span class="keyword">continue</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">0</span>]&amp;&amp;a[i][<span class="number">1</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">0</span>]++;</span><br><span class="line">				ans[<span class="number">1</span>]++;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">0</span>]&amp;&amp;a[i][<span class="number">2</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">0</span>]++;</span><br><span class="line">				ans[<span class="number">2</span>]++;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">1</span>]&amp;&amp;a[i][<span class="number">2</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">1</span>]++;</span><br><span class="line">				ans[<span class="number">2</span>]++;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">0</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">0</span>]+=<span class="number">3</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">1</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">1</span>]+=<span class="number">3</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">2</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">2</span>]+=<span class="number">3</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;<span class="number">3</span>;i++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>,ans[i]);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


<h2 id="逆序k倍对"><a href="#逆序k倍对" class="headerlink" title="逆序k倍对"></a>逆序k倍对</h2><p><img src="/.io//image-20230922102005428.png" alt="image-20230922102005428"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="type">int</span> a[<span class="number">1000002</span>], n, k, num;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">long</span> <span class="type">long</span> <span class="title">reversePairsRecursive</span><span class="params">(<span class="type">int</span>* nums, <span class="type">int</span> left, <span class="type">int</span> right)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (left == right) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">		<span class="type">int</span> mid = (left + right) / <span class="number">2</span>;</span><br><span class="line">		<span class="type">int</span> n1 = <span class="built_in">reversePairsRecursive</span>(nums, left, mid);</span><br><span class="line">		<span class="type">int</span> n2 = <span class="built_in">reversePairsRecursive</span>(nums, mid + <span class="number">1</span>, right);</span><br><span class="line">		<span class="type">long</span> <span class="type">long</span> ret = n1 + n2;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> i = left;</span><br><span class="line">		<span class="type">int</span> j = mid + <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">while</span> (i &lt;= mid) &#123;</span><br><span class="line">			<span class="keyword">while</span> (j &lt;= right &amp;&amp; (<span class="type">long</span> <span class="type">long</span>)nums[i] &gt; k * (<span class="type">long</span> <span class="type">long</span>)nums[j]) j++;</span><br><span class="line">			ret += (j - mid - <span class="number">1</span>) ;</span><br><span class="line">			i++;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> sorted[right - left + <span class="number">1</span>];</span><br><span class="line">		<span class="type">int</span> p1 = left, p2 = mid + <span class="number">1</span>;</span><br><span class="line">		<span class="type">int</span> p = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">while</span> (p1 &lt;= mid || p2 &lt;= right) &#123;</span><br><span class="line">			<span class="keyword">if</span> (p1 &gt; mid) &#123;</span><br><span class="line">				sorted[p++] = nums[p2++];</span><br><span class="line">			&#125; <span class="keyword">else</span> <span class="keyword">if</span> (p2 &gt; right) &#123;</span><br><span class="line">				sorted[p++] = nums[p1++];</span><br><span class="line">			&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">				<span class="keyword">if</span> (nums[p1] &lt; nums[p2]) &#123;</span><br><span class="line">					sorted[p++] = nums[p1++];</span><br><span class="line">				&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">					sorted[p++] = nums[p2++];</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; right - left + <span class="number">1</span>; i++) &#123;</span><br><span class="line">			nums[left + i] = sorted[i];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> ret;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">reversePairs</span><span class="params">(<span class="type">int</span>* nums, <span class="type">int</span> numsSize)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (numsSize == <span class="number">0</span>) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="built_in">reversePairsRecursive</span>(nums, <span class="number">0</span>, numsSize - <span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d %d&quot;</span>,&amp;n,&amp;k);</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n ; i++) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a[i]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;%lld\n&quot;</span>,<span class="built_in">reversePairs</span>(a,n));</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h1 id="E1"><a href="#E1" class="headerlink" title="E1"></a>E1</h1><h2 id="A-你还记得我嘛-多项式加法"><a href="#A-你还记得我嘛-多项式加法" class="headerlink" title="A 你还记得我嘛~(多项式加法)"></a>A 你还记得我嘛~(多项式加法)</h2><p><img src="/.io//image-20230922103338426.png" alt="image-20230922103338426"></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 200086</span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n, m, k;</span><br><span class="line"><span class="type">int</span> a[maxn], A[maxn], b[maxn], B[maxn], c[maxn], C[maxn];</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span> (t--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;a[i]);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;A[i]);</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;m);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m; i++)</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;b[i]);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m; i++)</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;B[i]);</span><br><span class="line">		<span class="type">int</span> posa = <span class="number">1</span>, posb = <span class="number">1</span>;</span><br><span class="line">		k = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">while</span> (posa &lt;= n || posb &lt;= m)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">if</span> (posa &gt; n)</span><br><span class="line">				c[++k] = b[posb], C[k] = B[posb], posb++;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span> (posb &gt; m)</span><br><span class="line">				c[++k] = a[posa], C[k] = A[posa], posa++;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span> (A[posa] == B[posb])</span><br><span class="line">				c[++k] = a[posa] + b[posb], C[k] = A[posa], posa++, posb++;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span> (A[posa] &lt; B[posb])</span><br><span class="line">				c[++k] = a[posa], C[k] = A[posa], posa++;</span><br><span class="line">			<span class="keyword">else</span></span><br><span class="line">				c[++k] = b[posb], C[k] = B[posb], posb++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, k);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= k; i++)</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, c[i]);</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= k; i++)</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, C[i]);</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="B-n次方的和"><a href="#B-n次方的和" class="headerlink" title="B n次方的和"></a>B n次方的和</h2><p><img src="/.io//image-20230922104158887.png" alt="image-20230922104158887"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;math.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> t;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="type">int</span> k, z, index = <span class="number">0</span>;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;z,&amp;k);</span><br><span class="line">		<span class="keyword">if</span> (k &gt; <span class="number">2</span>)</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;0\n&quot;</span>);</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>( k == <span class="number">1</span>)</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, z<span class="number">-1</span>);</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">for</span>(<span class="type">long</span> <span class="type">long</span> i = <span class="number">1</span>; i &lt; z; i++) &#123;</span><br><span class="line">				<span class="type">double</span> j = <span class="built_in">sqrt</span>(<span class="number">1ll</span> * z * z - i * i);</span><br><span class="line">				<span class="keyword">if</span>(j == (<span class="type">int</span>)j) &#123;</span><br><span class="line">					index++;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,index);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<h2 id="多路归并"><a href="#多路归并" class="headerlink" title="多路归并"></a>多路归并</h2><p><img src="/.io//image-20230922104257685.png" alt="image-20230922104257685"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 100086</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, k, n;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;k, &amp;n);</span><br><span class="line">		<span class="function">vector&lt;<span class="type">int</span>&gt; <span class="title">v</span><span class="params">(k * n)</span></span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; k * n; i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;v[i]);</span><br><span class="line">		<span class="built_in">sort</span>(v.<span class="built_in">begin</span>(), v.<span class="built_in">end</span>());</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">auto</span> x : v) <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, x);</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="D-随机数"><a href="#D-随机数" class="headerlink" title="D 随机数"></a>D 随机数</h2><p><img src="/.io//image-20230922104542514.png" alt="image-20230922104542514"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 20000086</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">unsigned</span> seed;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">Rand</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	seed ^= seed &lt;&lt; <span class="number">13</span>;</span><br><span class="line">	seed ^= seed &gt;&gt; <span class="number">7</span>;</span><br><span class="line">	seed ^= seed &lt;&lt; <span class="number">17</span>;</span><br><span class="line">	<span class="keyword">return</span> seed &amp; ((<span class="number">1</span> &lt;&lt; <span class="number">24</span>) - <span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n, a[maxn];</span><br><span class="line"><span class="type">int</span> num[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="built_in">memset</span>(num, <span class="number">0</span>, <span class="built_in">sizeof</span>(num));</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%u&quot;</span>, &amp;n, &amp;seed);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) a[i] = <span class="built_in">Rand</span>(), num[a[i]]++;</span><br><span class="line">		<span class="type">unsigned</span> ans = <span class="number">0</span>;</span><br><span class="line">		<span class="type">int</span> cnt = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt;= (<span class="number">1</span> &lt;&lt; <span class="number">24</span>) - <span class="number">1</span>; i++) &#123;</span><br><span class="line">			<span class="keyword">while</span>(num[i]--) cnt++, ans += i ^ cnt;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%u\n&quot;</span>, ans);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="组合数"><a href="#组合数" class="headerlink" title="组合数"></a>组合数</h2><p><img src="/.io//image-20230922105924398.png" alt="image-20230922105924398"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n, m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;m);</span><br><span class="line">		m = <span class="built_in">min</span>(m, n - m);</span><br><span class="line">		<span class="type">long</span> <span class="type">long</span> x = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m &amp;&amp; x &lt;= <span class="number">1e9</span>; i++) x *= n - i + <span class="number">1</span>, x /= i;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, x &lt;= <span class="number">1e9</span> ? x : <span class="number">-1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="F-莫卡的二叉树魔法"><a href="#F-莫卡的二叉树魔法" class="headerlink" title="F 莫卡的二叉树魔法"></a>F 莫卡的二叉树魔法</h2><p><img src="/.io//image-20230922110108059.png" alt="image-20230922110108059"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MIN(a,b) a&lt;b?a:b</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line">vector&lt;<span class="type">int</span>&gt;a[<span class="number">100005</span>];</span><br><span class="line"><span class="type">int</span> b[<span class="number">100005</span>];</span><br><span class="line"><span class="type">bool</span> path[<span class="number">100005</span>];</span><br><span class="line"><span class="type">char</span> s[<span class="number">100010</span>];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> u)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(a[u].<span class="built_in">empty</span>()) &#123;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;a[u].<span class="built_in">size</span>(); i++) &#123;</span><br><span class="line">		b[a[u][i]]^=b[u];</span><br><span class="line">		<span class="built_in">dfs</span>(a[u][i]);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> n,q;</span><br><span class="line">	<span class="type">int</span> x;</span><br><span class="line">	<span class="type">int</span> T;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;T);</span><br><span class="line">	<span class="keyword">while</span>(T--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) a[i].<span class="built_in">clear</span>(), b[i] = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>; i&lt;=n; i++) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">			a[x].<span class="built_in">push_back</span>(i);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,s);</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;q);</span><br><span class="line">		<span class="keyword">while</span>(q--) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">			b[x]^=<span class="number">1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">dfs</span>(<span class="number">1</span>);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;n; i++) &#123;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,(s[i]-<span class="string">&#x27;0&#x27;</span>)^b[i+<span class="number">1</span>]);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="2的幂"><a href="#2的幂" class="headerlink" title="2的幂"></a>2的幂</h2><p><img src="/.io//image-20230922111251560.png" alt="image-20230922111251560"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">55</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> inf = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">getint</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">char</span> c;</span><br><span class="line">	<span class="type">bool</span> flag = <span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> num = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span> ((c = <span class="built_in">getchar</span>()) &lt; <span class="string">&#x27;0&#x27;</span> || c &gt; <span class="string">&#x27;9&#x27;</span>)</span><br><span class="line">		<span class="keyword">if</span> (c == <span class="string">&#x27;-&#x27;</span>)</span><br><span class="line">			flag = <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">while</span> (c &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; c &lt;= <span class="string">&#x27;9&#x27;</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		num = num * <span class="number">10</span> + c - <span class="number">48</span>;</span><br><span class="line">		c = <span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> flag ? -num : num;</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">int</span> A[N], B[N];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">match</span><span class="params">(<span class="type">int</span> x, ll target)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> n = <span class="number">0</span>, m = <span class="number">0</span>, i, j;</span><br><span class="line">	<span class="keyword">while</span> (x)</span><br><span class="line">		A[++n] = x % <span class="number">10</span>, x /= <span class="number">10</span>;</span><br><span class="line">	<span class="keyword">while</span> (target)</span><br><span class="line">		B[++m] = target % <span class="number">10</span>, target /= <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">for</span> (i = m, j = n; i &amp;&amp; j; i--, j--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">for</span> (; j &amp;&amp; B[i] != A[j]; j--)</span><br><span class="line">			;</span><br><span class="line">		<span class="keyword">if</span> (j &lt;= <span class="number">0</span>)</span><br><span class="line">			<span class="keyword">break</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="type">int</span> delete_num = n - (m - i);</span><br><span class="line">	<span class="type">int</span> add_num = i;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> delete_num + add_num;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> T = <span class="built_in">getint</span>();</span><br><span class="line">	<span class="keyword">while</span> (T--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="type">int</span> n = <span class="built_in">getint</span>(), ans = inf;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt;= <span class="number">60</span>; i++)</span><br><span class="line">			ans = <span class="built_in">min</span>(ans, <span class="built_in">match</span>(n, <span class="number">1ll</span> &lt;&lt; i));</span><br><span class="line">		cout &lt;&lt; ans &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="I-XIAO7-的地图"><a href="#I-XIAO7-的地图" class="headerlink" title="I XIAO7 的地图"></a>I XIAO7 的地图</h2><p><img src="/.io//image-20230922112139921.png" alt="image-20230922112139921"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> index_list[<span class="number">11</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line"><span class="type">int</span> box[<span class="number">2047</span>][<span class="number">2047</span>] = &#123;&#123;<span class="number">0</span>&#125;&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">//turn为1表示顺时针旋转90°， turn为-1表示逆时针旋转90°， turn为0表示不旋转</span></span><br><span class="line">vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; <span class="built_in">draw_map</span>(<span class="type">int</span> x, <span class="type">int</span> y, <span class="type">int</span> index, <span class="type">int</span> turn) &#123;</span><br><span class="line">    vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw;</span><br><span class="line">    <span class="comment">//添加点</span></span><br><span class="line">    <span class="keyword">if</span> (index == <span class="number">1</span>) &#123;</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">0</span>,y + <span class="number">0</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">1</span>,y + <span class="number">0</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">2</span>,y + <span class="number">0</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">2</span>,y + <span class="number">1</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">2</span>,y + <span class="number">2</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">1</span>,y + <span class="number">2</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">0</span>,y + <span class="number">2</span>));</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="comment">//递归绘制四个子图</span></span><br><span class="line">        vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw1 = <span class="built_in">draw_map</span>(x, y, index - <span class="number">1</span>, <span class="number">1</span>);</span><br><span class="line">        vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw2 = <span class="built_in">draw_map</span>(x + index_list[index<span class="number">-1</span>] + <span class="number">1</span>, y, index - <span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line">        vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw3 = <span class="built_in">draw_map</span>(x, y + index_list[index<span class="number">-1</span>] + <span class="number">1</span>, index - <span class="number">1</span>, <span class="number">-1</span>);</span><br><span class="line">        vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw4 = <span class="built_in">draw_map</span>(x + index_list[index<span class="number">-1</span>] + <span class="number">1</span>, y + index_list[index<span class="number">-1</span>] + <span class="number">1</span>, index - <span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line">        draw.<span class="built_in">insert</span>(draw.<span class="built_in">end</span>(), draw1.<span class="built_in">begin</span>(), draw1.<span class="built_in">end</span>());</span><br><span class="line">        draw.<span class="built_in">insert</span>(draw.<span class="built_in">end</span>(), draw2.<span class="built_in">begin</span>(), draw2.<span class="built_in">end</span>());</span><br><span class="line">        draw.<span class="built_in">insert</span>(draw.<span class="built_in">end</span>(), draw3.<span class="built_in">begin</span>(), draw3.<span class="built_in">end</span>());</span><br><span class="line">        draw.<span class="built_in">insert</span>(draw.<span class="built_in">end</span>(), draw4.<span class="built_in">begin</span>(), draw4.<span class="built_in">end</span>());</span><br><span class="line">        <span class="comment">//绘制三个连接点</span></span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + index_list[index<span class="number">-1</span>],y));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + index_list[index<span class="number">-1</span>] + <span class="number">1</span>,y + index_list[index<span class="number">-1</span>]));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + index_list[index<span class="number">-1</span>],y + <span class="number">2</span> * index_list[index<span class="number">-1</span>]));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//处理旋转(瞬时针旋转90°)</span></span><br><span class="line">    <span class="keyword">if</span> (turn == <span class="number">1</span> || turn == <span class="number">-1</span>) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">auto</span> &amp;it:draw) &#123;</span><br><span class="line">            <span class="type">int</span> off_x = it.first - x;</span><br><span class="line">            <span class="type">int</span> off_y = it.second - y;</span><br><span class="line">            it.first = x + off_y;</span><br><span class="line">            it.second = y + off_x;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//上下对称</span></span><br><span class="line">    <span class="keyword">if</span> (turn == <span class="number">-1</span>) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">auto</span> &amp;it:draw) &#123;</span><br><span class="line">            <span class="type">int</span> off_y = it.second - y;</span><br><span class="line">            it.second = y + index_list[index] - <span class="number">1</span> - off_y;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> draw;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    cin &gt;&gt; n;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt; <span class="number">11</span>; i++) &#123;</span><br><span class="line">        index_list[i] = <span class="built_in">pow</span>(<span class="number">2</span>, i + <span class="number">1</span>) - <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw_final = <span class="built_in">draw_map</span>(<span class="number">0</span>,<span class="number">0</span>,n,<span class="number">0</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">auto</span> it:draw_final) &#123;</span><br><span class="line">        box[it.second][it.first] = <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//绘图</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="built_in">pow</span>(<span class="number">2</span>,n + <span class="number">1</span>) - <span class="number">1</span>; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; <span class="built_in">pow</span>(<span class="number">2</span>, n + <span class="number">1</span>) - <span class="number">1</span>; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (box[i][j] == <span class="number">1</span>) &#123;</span><br><span class="line">                cout &lt;&lt; <span class="string">&quot;*&quot;</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                cout &lt;&lt; <span class="string">&quot; &quot;</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        cout &lt;&lt; endl;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="C2"><a href="#C2" class="headerlink" title="C2"></a>C2</h1><h2 id="平面最近点对"><a href="#平面最近点对" class="headerlink" title="平面最近点对"></a>平面最近点对</h2><p><img src="/.io//image-20230922142257679.png" alt="image-20230922142257679"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 1005</span></span><br><span class="line"><span class="keyword">using</span> ll = <span class="type">long</span> <span class="type">long</span>;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">int</span> t, n, x[maxn], y[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, x + i), <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, y + i);</span><br><span class="line">		<span class="type">int</span> ans = <span class="number">200000</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) </span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt; i; j++) </span><br><span class="line">                ans = <span class="built_in">min</span>(ans, <span class="built_in">max</span>(<span class="built_in">abs</span>(x[i] - x[j]), <span class="built_in">abs</span>(y[i] - y[j])));</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<h2 id="B-最大堆的实现"><a href="#B-最大堆的实现" class="headerlink" title="B 最大堆的实现"></a>B 最大堆的实现</h2><p><img src="/.io//image-20230922142531892.png" alt="image-20230922142531892"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 1000005</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ls(x) (x &lt;&lt; 1)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> rs(x) (x &lt;&lt; 1 | 1)</span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> n, sz, a[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">swap</span><span class="params">(<span class="type">int</span> *a, <span class="type">int</span> *b)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> t = *a;</span><br><span class="line">	*a = *b, *b = t;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">maxHeapify</span><span class="params">(<span class="type">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> l = <span class="built_in">ls</span>(x), r = <span class="built_in">rs</span>(x), larg;</span><br><span class="line">	<span class="keyword">if</span>(l &lt;= sz &amp;&amp; a[l] &gt; a[x]) larg = l;</span><br><span class="line">	<span class="keyword">else</span> larg = x;</span><br><span class="line">	<span class="keyword">if</span>(r &lt;= sz &amp;&amp; a[r] &gt; a[larg]) larg = r;</span><br><span class="line">	<span class="keyword">if</span>(larg != x) <span class="built_in">swap</span>(&amp;a[x], &amp;a[larg]), <span class="built_in">maxHeapify</span>(larg);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">increaseKey</span><span class="params">(<span class="type">int</span> i, <span class="type">int</span> key)</span> </span>&#123;</span><br><span class="line">	a[i] = key;</span><br><span class="line">	<span class="keyword">while</span>(i &gt; <span class="number">1</span> &amp;&amp; a[i / <span class="number">2</span>] &lt; a[i]) &#123;</span><br><span class="line">		<span class="built_in">swap</span>(&amp;a[i / <span class="number">2</span>], &amp;a[i]);</span><br><span class="line">		i = i / <span class="number">2</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">insert</span><span class="params">(<span class="type">int</span> x)</span> </span>&#123;</span><br><span class="line">	sz += <span class="number">1</span>;</span><br><span class="line">	a[sz] = -inf;</span><br><span class="line">	<span class="built_in">increaseKey</span>(sz, x);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">top</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">return</span> a[<span class="number">1</span>];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(sz &lt; <span class="number">1</span>) <span class="built_in">exit</span>(<span class="number">1</span>);</span><br><span class="line">	a[<span class="number">1</span>] = a[sz];</span><br><span class="line">	sz -= <span class="number">1</span>;</span><br><span class="line">	<span class="built_in">maxHeapify</span>(<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">	<span class="type">int</span> i;</span><br><span class="line">	<span class="keyword">for</span>(i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">		<span class="type">int</span> op, x;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;op);</span><br><span class="line">		<span class="keyword">if</span>(op == <span class="number">1</span>) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;x);</span><br><span class="line">			<span class="built_in">insert</span>(x);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(op == <span class="number">2</span>) <span class="built_in">pop</span>();</span><br><span class="line">		<span class="keyword">if</span>(op == <span class="number">3</span>) <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, <span class="built_in">top</span>());</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span>(sz) &#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, <span class="built_in">top</span>()), <span class="built_in">pop</span>();</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h1 id="E2"><a href="#E2" class="headerlink" title="E2"></a>E2</h1><h2 id="A-简单的可删堆"><a href="#A-简单的可删堆" class="headerlink" title="A 简单的可删堆"></a>A 简单的可删堆</h2><p><img src="/.io//image-20230922144420311.png" alt="image-20230922144420311"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;math.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;ctype.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> pi acos(-1)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 2147483647</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> llinf 9223372036854775807</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MIN(a,b) (a&lt;b?a:b)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX(a,b) (a&gt;b?a:b)</span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> N 200010</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">swap</span><span class="params">(<span class="type">int</span> *a,<span class="type">int</span> *b)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> t=*a;</span><br><span class="line">	*a=*b;</span><br><span class="line">	*b=t;</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">int</span> heap_size=<span class="number">0</span>;</span><br><span class="line"><span class="type">int</span> heap[N];</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> heapDel_size=<span class="number">0</span>;</span><br><span class="line"><span class="type">int</span> heapDel[N];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">put</span><span class="params">(<span class="type">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> now,next,res;</span><br><span class="line">	heap[++heap_size]=x;</span><br><span class="line">	now=heap_size;</span><br><span class="line">	<span class="keyword">while</span>(now&gt;<span class="number">1</span>) &#123;</span><br><span class="line">		next=now&gt;&gt;<span class="number">1</span>;</span><br><span class="line">		<span class="keyword">if</span>(heap[now]&gt;=heap[next]) &#123;</span><br><span class="line">			<span class="keyword">return</span>;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="built_in">swap</span>(&amp;heap[now],&amp;heap[next]);</span><br><span class="line">			now=next;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">get</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(heap_size&lt;<span class="number">1</span>)<span class="built_in">exit</span>(<span class="number">-1</span>);</span><br><span class="line">	<span class="keyword">return</span> heap[<span class="number">1</span>];</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">del</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(heap_size&lt;<span class="number">1</span>)<span class="built_in">exit</span>(<span class="number">-1</span>);</span><br><span class="line">	<span class="type">int</span> res=heap[<span class="number">1</span>];</span><br><span class="line">	heap[<span class="number">1</span>]=heap[heap_size--];</span><br><span class="line">	<span class="type">int</span> now=<span class="number">1</span>,next;</span><br><span class="line">	<span class="keyword">while</span>(now*<span class="number">2</span>&lt;=heap_size) &#123;</span><br><span class="line">		next=now*<span class="number">2</span>;</span><br><span class="line">		<span class="keyword">if</span>(next&lt;heap_size&amp;&amp;heap[next+<span class="number">1</span>]&lt;heap[next]) &#123;</span><br><span class="line">			next++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(heap[now]&lt;=heap[next]) &#123;</span><br><span class="line">			<span class="keyword">return</span> res;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">swap</span>(&amp;heap[now],&amp;heap[next]);</span><br><span class="line">		now=next;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">putDel</span><span class="params">(<span class="type">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> now,next,res;</span><br><span class="line">	heapDel[++heapDel_size]=x;</span><br><span class="line">	now=heapDel_size;</span><br><span class="line">	<span class="keyword">while</span>(now&gt;<span class="number">1</span>) &#123;</span><br><span class="line">		next=now&gt;&gt;<span class="number">1</span>;</span><br><span class="line">		<span class="keyword">if</span>(heapDel[now]&gt;=heapDel[next]) &#123;</span><br><span class="line">			<span class="keyword">return</span>;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="built_in">swap</span>(&amp;heapDel[now],&amp;heapDel[next]);</span><br><span class="line">			now=next;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">getDel</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(heapDel_size&lt;<span class="number">1</span>)<span class="keyword">return</span> <span class="number">-2</span>;</span><br><span class="line">	<span class="keyword">return</span> heapDel[<span class="number">1</span>];</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">delDel</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> res=heapDel[<span class="number">1</span>];</span><br><span class="line">	heapDel[<span class="number">1</span>]=heapDel[heapDel_size--];</span><br><span class="line">	<span class="type">int</span> now=<span class="number">1</span>,next;</span><br><span class="line">	<span class="keyword">while</span>(now*<span class="number">2</span>&lt;=heapDel_size) &#123;</span><br><span class="line">		next=now*<span class="number">2</span>;</span><br><span class="line">		<span class="keyword">if</span>(next&lt;heapDel_size&amp;&amp;heapDel[next+<span class="number">1</span>]&lt;heapDel[next]) &#123;</span><br><span class="line">			next++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(heapDel[now]&lt;=heapDel[next]) &#123;</span><br><span class="line">			<span class="keyword">return</span> res;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">swap</span>(&amp;heapDel[now],&amp;heapDel[next]);</span><br><span class="line">		now=next;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> n,op,x;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">	<span class="keyword">while</span>(n--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;op);</span><br><span class="line">		<span class="keyword">if</span>(op==<span class="number">1</span>) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">			<span class="built_in">put</span>(x);</span><br><span class="line">		&#125; <span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">2</span>) &#123;</span><br><span class="line">			<span class="keyword">while</span>(<span class="built_in">get</span>()==<span class="built_in">getDel</span>()) &#123;</span><br><span class="line">				<span class="built_in">del</span>();</span><br><span class="line">				<span class="built_in">delDel</span>();</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="built_in">del</span>();</span><br><span class="line">		&#125; <span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">3</span>) &#123;</span><br><span class="line">			<span class="keyword">while</span>(<span class="built_in">get</span>()==<span class="built_in">getDel</span>()) &#123;</span><br><span class="line">				<span class="built_in">del</span>();</span><br><span class="line">				<span class="built_in">delDel</span>();</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,<span class="built_in">get</span>());</span><br><span class="line">		&#125; <span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">4</span>) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">			<span class="built_in">putDel</span>(x);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span>(heap_size&gt;<span class="number">0</span>) &#123;</span><br><span class="line">		<span class="keyword">if</span>(<span class="built_in">get</span>()==<span class="built_in">getDel</span>()) &#123;</span><br><span class="line">			<span class="built_in">del</span>();</span><br><span class="line">			<span class="built_in">delDel</span>();</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>,<span class="built_in">del</span>());</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="B-递归铺瓷砖"><a href="#B-递归铺瓷砖" class="headerlink" title="B 递归铺瓷砖"></a>B 递归铺瓷砖</h2><p><img src="/.io//image-20230922145722701.png" alt="image-20230922145722701"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (i = <span class="number">6</span>; i &lt; M; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		result[i] = (result[i - <span class="number">1</span>] + result[i - <span class="number">2</span>] + <span class="number">4</span> * result[i - <span class="number">3</span>] + <span class="number">2</span> * result[i - <span class="number">4</span>] + <span class="number">2</span> * sum[i - <span class="number">3</span>]) % MOD;</span><br><span class="line">    <span class="comment">// sum的来源：铺满长度为 n-i (i &gt; 4)的地板后，可以用棕色弯块，拼接i-3个绿色短块，再拼接灰色弯块或黄绿色弯块；或者使用粉色弯块，拼接i-3个绿色短块，再拼接灰色弯块或黄绿色弯块</span></span><br><span class="line">		sum[i] = (sum[i - <span class="number">1</span>] + result[i]) % MOD;</span><br><span class="line">	&#125;</span><br></pre></td></tr></table></figure>



<h2 id="C-子集"><a href="#C-子集" class="headerlink" title="C 子集"></a>C 子集</h2><p><img src="/.io//image-20230922151222239.png" alt="image-20230922151222239"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n, m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--)&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;m);</span><br><span class="line">		<span class="type">int</span> ans = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= (n + <span class="number">1</span>) / <span class="number">2</span>;i++) ans *= n - i + <span class="number">1</span>, ans /= i;</span><br><span class="line">		<span class="keyword">if</span>(ans &lt; m)&#123;</span><br><span class="line">			<span class="built_in">puts</span>(<span class="string">&quot;-1&quot;</span>);</span><br><span class="line">			<span class="keyword">continue</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i &lt; (<span class="number">1</span> &lt;&lt; n) &amp;&amp; m;i++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(__builtin_popcount(i) == (n + <span class="number">1</span>) / <span class="number">2</span>)&#123;</span><br><span class="line">				m--;</span><br><span class="line">				<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, (n + <span class="number">1</span>) / <span class="number">2</span>);</span><br><span class="line">				<span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>;j &lt; n;j++) </span><br><span class="line">                    <span class="keyword">if</span>(i &amp; (<span class="number">1</span> &lt;&lt; j)) </span><br><span class="line">                        <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, j + <span class="number">1</span>);</span><br><span class="line">                <span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>); </span><br><span class="line">            &#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<h2 id="汉诺塔"><a href="#汉诺塔" class="headerlink" title="汉诺塔"></a>汉诺塔</h2><p><img src="/.io//image-20230922151900640.png" alt="image-20230922151900640"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 1e18</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 20005</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">unsigned</span> <span class="type">long</span> <span class="type">long</span> ull;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> ll mod = <span class="number">998244353</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">double</span> eps = <span class="number">1e-4</span>;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> ll <span class="title">read</span><span class="params">()</span></span>&#123;</span><br><span class="line">    ll x = <span class="number">0</span>, f = <span class="number">1</span>;<span class="type">char</span> ch = <span class="built_in">getchar</span>();</span><br><span class="line">    <span class="keyword">while</span>(ch &gt; <span class="string">&#x27;9&#x27;</span> || ch &lt; <span class="string">&#x27;0&#x27;</span>)&#123;<span class="keyword">if</span>(ch == <span class="string">&#x27;-&#x27;</span>) f = <span class="number">-1</span>;ch = <span class="built_in">getchar</span>();&#125;</span><br><span class="line">    <span class="keyword">while</span>(ch &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; ch &lt;= <span class="string">&#x27;9&#x27;</span>)&#123;x = x * <span class="number">10</span> + ch -<span class="string">&#x27;0&#x27;</span>;ch = <span class="built_in">getchar</span>();&#125;</span><br><span class="line">    <span class="keyword">return</span> x * f;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> n;</span><br><span class="line"><span class="type">char</span> s[maxn];</span><br><span class="line"></span><br><span class="line"><span class="type">char</span> pan[<span class="number">5</span>] = &#123;<span class="string">&#x27; &#x27;</span>, <span class="string">&#x27;A&#x27;</span>, <span class="string">&#x27;B&#x27;</span>, <span class="string">&#x27;C&#x27;</span>&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">solve</span><span class="params">(<span class="type">int</span> n, <span class="type">int</span> now, <span class="type">int</span> to)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(n == <span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(to == now % <span class="number">3</span> + <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span>(s[n] == <span class="string">&#x27;r&#x27;</span>) <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[now], pan[to]);</span><br><span class="line">            <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[now], pan[<span class="number">6</span> - now - to]), <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[<span class="number">6</span> - now - to], pan[to]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">if</span>(s[n] == <span class="string">&#x27;l&#x27;</span>) <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[now], pan[to]);</span><br><span class="line">            <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[now], pan[<span class="number">6</span> - now - to]), <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[<span class="number">6</span> - now - to], pan[to]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(to == now % <span class="number">3</span> + <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span>(s[n] == <span class="string">&#x27;r&#x27;</span>) <span class="built_in">solve</span>(n - <span class="number">1</span>, now, <span class="number">6</span> - now - to), <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[now], pan[to]), <span class="built_in">solve</span>(n - <span class="number">1</span>, <span class="number">6</span> - now - to, to);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, now, to);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[now], pan[<span class="number">6</span> - now - to]);</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, to, now);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n,  pan[<span class="number">6</span> - now - to], pan[to]);</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, now, to);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(s[n] == <span class="string">&#x27;l&#x27;</span>) <span class="built_in">solve</span>(n - <span class="number">1</span>, now, <span class="number">6</span> - now - to),<span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[now], pan[to]), <span class="built_in">solve</span>(n - <span class="number">1</span>, <span class="number">6</span> - now - to, to);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, now, to);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[now], pan[<span class="number">6</span> - now - to]);</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, to, now);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[<span class="number">6</span> - now - to], pan[to]);</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, now, to);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d%s&quot;</span>, &amp;n, s + <span class="number">1</span>) != EOF)&#123;</span><br><span class="line">        <span class="built_in">solve</span>(n, <span class="number">1</span>, <span class="number">3</span>);</span><br><span class="line">        <span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h1 id="C7"><a href="#C7" class="headerlink" title="C7"></a>C7</h1><h2 id="B-搬砖问题"><a href="#B-搬砖问题" class="headerlink" title="B 搬砖问题"></a>B 搬砖问题</h2><p><img src="/.io//image-20230922141545470.png" alt="image-20230922141545470"></p>
<p>看了一眼，确信直接贪心就好</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;ctime&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;assert.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> pair&lt;ll, ll&gt; pi;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">100005</span>;</span><br><span class="line"><span class="type">const</span> ll inf = <span class="number">1ll</span> &lt;&lt; <span class="number">60</span>;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">getint</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">char</span> c;</span><br><span class="line">	<span class="type">bool</span> flag=<span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> num=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>((c=<span class="built_in">getchar</span>())&lt;<span class="string">&#x27;0&#x27;</span>||c&gt;<span class="string">&#x27;9&#x27;</span>)<span class="keyword">if</span>(c==<span class="string">&#x27;-&#x27;</span>)flag=<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">while</span>(c&gt;=<span class="string">&#x27;0&#x27;</span>&amp;&amp;c&lt;=<span class="string">&#x27;9&#x27;</span>) &#123;</span><br><span class="line">		num=num*<span class="number">10</span>+c<span class="number">-48</span>;</span><br><span class="line">		c=<span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> flag ? -num : num;</span><br><span class="line">&#125;</span><br><span class="line">pi a[N];</span><br><span class="line">ll t[N];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="type">int</span> n;</span><br><span class="line">	<span class="type">int</span> tt;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;tt);</span><br><span class="line">	<span class="keyword">while</span>(tt--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">		<span class="built_in">assert</span>(n &lt;= <span class="number">1e5</span>);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i ++) &#123;</span><br><span class="line">			a[i].second = <span class="built_in">getint</span>();</span><br><span class="line">			a[i].first = <span class="built_in">getint</span>();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">sort</span>(a + <span class="number">1</span>, a + n + <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> T = <span class="built_in">getint</span>();</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= T; i ++) &#123;</span><br><span class="line">			t[i] = <span class="built_in">getint</span>();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">sort</span>(t + <span class="number">1</span>, t + T + <span class="number">1</span>), t[T + <span class="number">1</span>] = inf;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">		ll ans = <span class="number">0</span>, sum = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>, j = <span class="number">1</span>; i &lt;= n; ) &#123;</span><br><span class="line">			<span class="keyword">if</span>(sum + a[i].second &lt;= t[j])  &#123;</span><br><span class="line">				ans += <span class="number">1ll</span> * j * a[i].first * a[i].second;</span><br><span class="line">				sum += a[i].second, i ++;</span><br><span class="line">			&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">				ll m = t[j] - sum;</span><br><span class="line">				a[i].second -= m;</span><br><span class="line">				ans += <span class="number">1ll</span> * j * a[i].first * m;</span><br><span class="line">				sum += m, j ++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		cout &lt;&lt; ans &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="C-Bellalabella-与中位数"><a href="#C-Bellalabella-与中位数" class="headerlink" title="C Bellalabella 与中位数"></a>C Bellalabella 与中位数</h2><p><img src="/.io//image-20230922135427281.png" alt="image-20230922135427281"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> eps 1e-14</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 1000005</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ls (tot &lt;&lt; 1)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> rs (tot &lt;&lt; 1 | 1)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> PII pair<span class="string">&lt;int, int&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> fi first</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> se second</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">double</span> ld;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">unsigned</span> <span class="type">long</span> <span class="type">long</span> ull;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> <span class="type">double</span> pi = <span class="built_in">acosl</span>(<span class="number">-1.0L</span>);</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> mod = <span class="number">998244353</span>;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> ll <span class="title">read</span><span class="params">()</span></span>&#123;</span><br><span class="line">    ll x = <span class="number">0</span>, f = <span class="number">1</span>;<span class="type">char</span> ch = <span class="built_in">getchar</span>();</span><br><span class="line">    <span class="keyword">while</span>(ch &gt; <span class="string">&#x27;9&#x27;</span> || ch &lt; <span class="string">&#x27;0&#x27;</span>)&#123;<span class="keyword">if</span>(ch == <span class="string">&#x27;-&#x27;</span>) f = <span class="number">-1</span>;ch = <span class="built_in">getchar</span>();&#125;</span><br><span class="line">    <span class="keyword">while</span>(ch &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; ch &lt;= <span class="string">&#x27;9&#x27;</span>)&#123;x = x * <span class="number">10</span> + ch -<span class="string">&#x27;0&#x27;</span>;ch = <span class="built_in">getchar</span>();&#125;</span><br><span class="line">    <span class="keyword">return</span> x * f;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> n, a[maxn];</span><br><span class="line">priority_queue&lt;<span class="type">int</span>&gt; q;</span><br><span class="line">priority_queue&lt;<span class="type">int</span>, vector&lt;<span class="type">int</span>&gt;, greater&lt;<span class="type">int</span>&gt;&gt; p;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">solve</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(!q.<span class="built_in">empty</span>())q.<span class="built_in">pop</span>();</span><br><span class="line">	<span class="keyword">while</span>(!p.<span class="built_in">empty</span>())p.<span class="built_in">pop</span>();</span><br><span class="line">	n = <span class="built_in">read</span>();</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">		a[i] = <span class="built_in">read</span>();</span><br><span class="line">		q.<span class="built_in">push</span>(a[i]);</span><br><span class="line">		<span class="keyword">if</span>(i &amp; <span class="number">1</span>)&#123;</span><br><span class="line">			<span class="keyword">while</span>(q.<span class="built_in">size</span>() &gt; p.<span class="built_in">size</span>()) p.<span class="built_in">push</span>(q.<span class="built_in">top</span>()), q.<span class="built_in">pop</span>();</span><br><span class="line">			<span class="keyword">while</span>(q.<span class="built_in">size</span>() &lt; p.<span class="built_in">size</span>()) q.<span class="built_in">push</span>(p.<span class="built_in">top</span>()), p.<span class="built_in">pop</span>();</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, q.<span class="built_in">top</span>());</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="built_in">init</span>();</span><br><span class="line">	<span class="type">int</span> t = <span class="built_in">read</span>();</span><br><span class="line">	<span class="keyword">while</span>(t--)&#123;</span><br><span class="line">		<span class="built_in">solve</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


    </div>

    
    
    

    <footer class="post-footer"><script src="//sdk.jinrishici.com/v2/browser/jinrishici.js"></script>
<script>
  jinrishici.load((result) => {
    let jrsc = document.getElementById('jrsc');
    const data = result.data;
    let author = data.origin.author;
    let title = '《' + data.origin.title + '》';
    let content = data.content.substr(0, data.content.length - 1);
    let dynasty = data.origin.dynasty.substr(0, data.origin.dynasty.length - 1);
    jrsc.innerText = content + ' @ ' + dynasty + '·' + author + title;
  });
</script>
<div style="text-align: center"><span id="jrsc" >正在加载今日诗词....</span></div>


        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2023/09/21/%E8%A1%A5%E5%85%85%E6%9D%BF%E5%AD%90/" rel="prev" title="">
                  <i class="fa fa-chevron-left"></i> 
                </a>
            </div>
            <div class="post-nav-item">
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments" id="waline"></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Mathieu Lin</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div><script color="0,0,255" opacity="0.5" zIndex="-1" count="99" src="https://cdnjs.sourcegcdn.com//ajax/libs/canvas-nest.js/1.0.1/canvas-nest.js"></script>

    </div>
  </footer>

  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/next-theme-pjax/0.5.0/pjax.min.js" integrity="sha256-3NkoLDrmHLTYj7csHIZSr0MHAFTXth7Ua/DDt4MRUAg=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  
<script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.0/search.js" integrity="sha256-vXZMYLEqsROAXkEw93GGIvaB2ab+QW6w3+1ahD9nXXA=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>





  




<script class="next-config" data-name="waline" type="application/json">{"lang":"zh-CN","enable":true,"serverURL":"https://blog-commeny-mh5e4d5jo-mathieulin.vercel.app","cssUrl":"https://unpkg.com/@waline/client@v2/dist/waline.css","commentCount":true,"pageview":false,"el":"#waline","comment":true,"libUrl":"//unpkg.com/@waline/client@v2/dist/waline.js","path":"/2023/09/22/super2121/"}</script>
<link rel="stylesheet" href="https://unpkg.com/@waline/client@v2/dist/waline.css">
<script>
document.addEventListener('page:loaded', () => {
  NexT.utils.loadComments(CONFIG.waline.el).then(() =>
    NexT.utils.getScript(CONFIG.waline.libUrl, { condition: window.Waline })
  ).then(() => 
    Waline.init(Object.assign({}, CONFIG.waline,{ el: document.querySelector(CONFIG.waline.el) }))
  );
});
</script>

</body>
</html>

<!-- 页面点击小红心 -->
<script type="text/javascript" src="/js/src/clicklove.js"></script>
